/*符合下列属性的数组 arr 称为 山脉数组 ：
* arr.length >= 3
* 存在 i（0 < i < arr.length - 1）使得：
* arr[0] < arr[1] < ... arr[i-1] < arr[i]
* arr[i] > arr[i+1] > ... > arr[arr.length - 1]
* 给你由整数组成的山脉数组 arr ，返回任何满足
* arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
*
* 输入：arr = [3,4,5,1]
* 输出：2
* */

package Leetcode;

public class leetcode852 {

    public static void main(String[] args) {

        leetcode852 obj = new leetcode852();
        int[] arr = {24,69,100,99,79,78,67,36,26,19};
        System.out.println(obj.peakIndexInMountainArray(arr));
    }

    public int peakIndexInMountainArray(int[] arr){

        //时间复杂度O(n)
//        for (int i = 0;i < arr.length;i++){
//
//            if (arr[i] > arr[i + 1]){
//                return i;
//            }
//        }
//        return 0;

        //采用二分法查找，时间复杂度O(logn)
        int left = 0, right = arr.length - 1, res = 0;
        while (left <= right){

            int pivot = (left + right) / 2;
            if (arr[pivot] > arr[pivot + 1]){
                res = pivot;
                right = pivot - 1;
            }else{
                left = pivot + 1;
            }
        }
        return res;
    }
}
